<?php
/**
 * 直接插入排序
 * 排序思想:每次从无序表中取出第一个元素，把它插入到有序表的合适位置，使有序表仍然有序。第一趟比较前两个数，然后把第二个数按大小插入到有序表中；
 * 第二趟把第三个数据与前两个数从前向后扫描，把第三个数按大小插入到有序表中；依次进行下去，进行了(n-1)趟扫描以后就完成了整个排序过程。
 * @author //github.com/yuesir
 */


/**
 * 直接插入排序
 * @param array $bucket
 * @return array
 */
function insertSort(array $bucket) {
    if ( empty($bucket) || 1 == count($bucket)) return $bucket;

    $sortedRes = [];
    $count = count($bucket);
    for ($i = 0; $i < $count; $i++) {
        $insertValue = $bucket[$i];
        if ( !isset($sortedRes[0])) $sortedRes[0] = $insertValue;

        $resCount = count($sortedRes);
        $insertPosition = 0;
        for ($j = 0; $j < $resCount; $j++) {
            if ($insertValue > $sortedRes[$j]) {
                $insertPosition = $j;
            }
        }
        array_splice($sortedRes, $insertPosition, 0, array($insertValue));

    }

    return $bucket;
}